#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stdlib.h>
#include <stdio.h>


using namespace std;

//define o que é um nó do grafo
struct No {

  int rank;
  int id;
  struct No *pai;

};


//define o que é aresta 
typedef struct {

  float proximidade;
  int ladoA;
  int ladoB;

}aresta;

//Variaveis globais
vector<aresta> arestas;
vector<No*> nos;
vector<string> categorias;
map<int, map<string, int> > clusters;
map<int, map<string, int> >::iterator it;
int qtdNos = 0;
//arquivos de entrada
FILE *grafo = fopen("graph.dat", "r");
FILE *categoriasData = fopen("categs.dat", "r");


//compara a proximidade das duas arestas
bool comparaAresta(aresta a, aresta b) {
  return a.proximidade < b.proximidade;
}

void inicializaNo(No *n, int id) {
  n->pai = n;
  n->rank = 0;
  n->id = id;
}


//encontra no inicial do grafo
No* encontraNoInicial(No *n) {
  if ( n->pai->id != n->id ) {
    n->pai = encontraNoInicial(n->pai);
  }
  return n->pai;
}

//agrega nos em um mesmo cluster ( colocando com o mesmo pai)
int juntaCluster(No *n1, No *n2) {


  No *inicial1 = encontraNoInicial(n1);
  No *inicial2 = encontraNoInicial(n2);

  //caso trivial
  if ( inicial1->id == inicial2->id ) return -1;

  if ( inicial1->rank < inicial2->rank ) inicial1->pai = inicial2->pai;
  else if ( inicial1->rank > inicial2->rank ) inicial2->pai = inicial1->pai; 
  else {
    inicial1->rank++;
    inicial2->pai = inicial1;
  }
  return 1;



}

//le dados de categoriasData
void le_categoriasData(){
  
  char aux[500];
  int inicial,id;
  string categoria;

  for (int i=0; i<qtdNos; i++) {
    encontraNoInicial(nos[i]);
    fscanf(categoriasData, "%*d %s\n", aux);
    categoria = aux;
    categorias.push_back(categoria);
  }

  for (int i=0; i<qtdNos; i++) {
    inicial = nos[i]->pai->id;
    id = nos[i]->id;
    categoria = categorias[id];
    if ( clusters[inicial].count(categoria) == 0 ) clusters[inicial][categoria] = 1;
    else clusters[inicial][categoria] += 1;
  }
}


//imprime solucao encontrada
void imprimeResultado(){

  int contador = 1;

  //itera sobre os clusters encontrados
  for (it=clusters.begin() ; it != clusters.end(); it++ )
  {

    printf("Cluster %d:", contador);

    for (int i=0; i<categorias.size()-1; i++)
    {
      if ( (*it).second.count(categorias[i]) != 0 ) printf(" %s = %d;", categorias[i].c_str(), (*it).second[categorias[i]]);
      else printf(" %s = 0;", categorias[i].c_str());
    }
    if ( (*it).second.count(categorias[categorias.size()-1]) != 0 ) printf(" %s = %d.", categorias[categorias.size()-1].c_str(), (*it).second[categorias[categorias.size()-1]]);
    else printf(" %s = 0.", categorias[categorias.size()-1].c_str());

    printf("\n");
    contador++;
  }

}


// encontra todos os N clusters pedidos
void encontraClusters(int arestas_size, int qtdClusters, int clustersPedidos){

	for (int i = 0;i < arestas_size;i++) {
	    if ( qtdClusters == clustersPedidos ) break;
	    if ( juntaCluster(nos[arestas[i].ladoA], nos[arestas[i].ladoB]) == 1 )
	      qtdClusters--;
	 }
}

//le o arquivo de arestas
void le_arestas(){

  aresta aux;
  int noA,noB;
  float proximidade;


  while ( fscanf(grafo, "%d %d %f\n", &noA, &noB, &proximidade) > 0) {

    aux.ladoA = noA;
    aux.ladoB = noB;
    aux.proximidade = proximidade;

    if ( noA < noB )  arestas.push_back(aux);
    if ( noA > qtdNos ) qtdNos = noA;
    if ( noB > qtdNos ) qtdNos = noB;

  }
  qtdNos++;


}

//inicializa todos os nos
void inicializaNos(){

  No *aux;

  for (int i=0; i<qtdNos; i++) {
    aux = (No*)malloc(sizeof(No));
    nos.push_back(aux);
    inicializaNo(nos[i], i);
  }


}



/*    MAIN    */
int main(int argc, char* argv[]) {


  //informa que nao foi passado quatidade de clusters desejada
  if ( argc < 2 )
  {
	 printf("Nao foi especificado a quantidade de clusters desejada\n");  
	 return 1;
  }
 
  //Clusters pedidos
  int clustersPedidos = atoi(argv[1]);


  //le informacoes de aresta
  le_arestas();  
 
  //le informacoes de nos
  inicializaNos();
 
  //ordena por proximidade entre artistas
  sort(arestas.begin(), arestas.end(), comparaAresta);


  int arestas_size = arestas.size();
  int qtdClusters = qtdNos;

  //encontra clusters
  encontraClusters(arestas_size, qtdClusters,clustersPedidos);
  
  //le os dados das categoriasData
  le_categoriasData();

  //ordena categoriasData por ordem alfabetica 	
  sort(categorias.begin(), categorias.end());

  categorias.resize(unique(categorias.begin(), categorias.end()) - categorias.begin());


  //imprime resultado
  imprimeResultado();
}
